package com.cuz.for2024;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

public class T40 {
    public static void main(String[] args) {
        System.out.println(new T40().combinationSum2(new int[]{10, 1, 2, 7, 6, 1, 5}, 8));
    }

    public List<List<Integer>> combinationSum2(int[] candidates, int target) {

        Arrays.sort(candidates);
        List<List<Integer>> res = new ArrayList<>();
        LinkedList<Integer> tempResult = new LinkedList<>();
        process(candidates, target, 0, res, tempResult);
        return res;
    }

    private void process(int[] candidates, int target,
                         int index, List<List<Integer>> res,
                         LinkedList<Integer> tempResult) {

        if (target == 0 && !tempResult.isEmpty()) {
            res.add(new ArrayList<>(tempResult));
            return;
        }
        if (index == candidates.length) {
            return;
        }
        if (candidates[index] > target) {
            return;
        }
        // 不用这个数
        process(candidates, target, index + 1, res, tempResult);


        int nowCanUse = candidates[index];
        if (nowCanUse > target) {
            return;
        }
        tempResult.addLast(nowCanUse);
        process(candidates, target - nowCanUse, index + 1, res, tempResult);
        tempResult.removeLast();
    }
}
